343. 整数拆分

题目链接
代码随想录

分析

我一开始看到这道题目的时候没有任何思路，但是我首先将 dp[i] 数组定义为，i 拆分成多个正整数之后，其乘积最大值，然后我推演了一下 i 从 2 到 10 的所有的 dp[i] 的值。
这里讲解一个重要多 dp 的技巧：dp 的大部分提都是用数学归纳法，而数学归纳法大部分都是永远求解数列问题的，所以只要你的 dp 定义的没错，你把 dp 的前 10 位推演出来，推演着推演着就有思路了。

• dp[2] 1
• dp[3] 2
• dp[4] 4
• dp[5] 6
• dp[6] 9
• dp[7] 12
• dp[8] 18
• dp[9] 27
  然后我在推演的时候就发现，当前 i 的最大值，可以拆解成之前求过的 dp 值和 i 与之的距离。比如 dp[8] 其实是等于 (8-6)*dp[6]， dp[9] 其实是等于 (9-6)*dp[6]，那到底应该选 i 减几呢？
  再经过仔细对比我们发现：
• i 如果减 1，其实 1*dp[i-1]，所以拆分出一个 1 来肯定不是乘积最大的时候的拆分方案。所以 i 至少减 2。
• 然后通过观察 dp[i] 的值，我们可以发现，从 5 开始，i 没有 dp[i] 大，什么意思呢？就是如果我拆分出一个 5，肯定不是乘积最大的方案，因为我把 5 再拆一次，会让结果更大。所以 i 最多减 4。
  因此，i 最少减 2，最多减 4，状态转移方程出来了：dp[i] = Math.max(Math.max(2 * dp[i - 2], 3 * dp[i - 3]), 4 * dp[i - 4])；
  然后我们开始确定初始值，我们可以看到 i<4 的时候，dp[i]< i，说明当一个数字小于 4 的时候，其实我们没有必要再拆了，再拆其实就会让最终的乘积更小，还不如直接乘以 i。此时，上面的状态转移方程是不正确的，除非你把 i 也作为比较对象包含进去，所以想要让上面的状态转移方程正确，dp[i] 中的 i 其实就必须大于等于 4，也就是 i-4>=4，i 从 8 开始计算。
  然后遍历顺序也确定了，其实就是从左到右。
  效率最高。但是非常不好想。很难在半个小时之内想出来。

然后我看了代码随想录的方案，了解到了一个简单的思路。
dp 数组的定义还是 i 拆分成多个正整数之后，其乘积最大值。但是求 dp[i] 的时候，用 for 循环所有拆成两个数的情况找出来，拆分出的两个数为 j 和 i-j，然后比较 j*(i-j) 跟 j*dp[i-j] 哪个更大，为什么不是拆分成 dp[j]*dp[i-j]，其实因为 j 是从 1 到 i-1，所以 j 实际上是已经把所有的情况都考虑在内了，比如 i 等于 10，当前 j 为 6，j 可以拆分成 2 和 4 ，那么当前应该计算 2*4*dp[4] ,但是因为 j 是从 1 开始遍历的，所以实际上我们已经遍历过了 j=2 和 j=4 的情况，j=2 时候，另一半为 dp[8]，j=4 时候，另一半为 dp[6]，这些乘积的大小我们前面也都比较过，也就是说，j 拆分与 j 不拆分的情况我们都已经对比过了。所以不会有问题。这一点确实有点不好理解。
我想出来的思路只用了一个 for 循环，这个标准方法用了 for 循环嵌套，所以效率会不高。
一开始我拒绝使用两层 for 循环的思路，其实用两层 for 循环也可以，不是用两层就代表不行。

解题

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[2] = 1;
    if (n == 2) {
        return dp[n];
    }
    dp[3] = 2;
    if (n == 3) {
        return dp[n];
    }
    dp[4] = 4;
    if (n == 4) {
        return dp[n];
    }
    dp[5] = 6;
    if (n == 5) {
        return dp[n];
    }
    dp[6] = 9;
    if (n == 6) {
        return dp[n];
    }
    dp[7] = 12;
    if (n == 7) {
        return dp[n];
    }
    for (int i = 8; i <= n; i++) {
        dp[i] = Math.max(Math.max(2 * dp[i - 2], 3 * dp[i - 3]), 4 * dp[i - 4]);
    }
    return dp[n];
}

容易想到的官方版本

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
        }
    }
    return dp[n];
}

相关题